from typing import List


class Solution:
    _MIN = 0
    _MAX = 10 ** 6 - 1

    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        # 整理禁止通行的方格
        blocks = set((x, y) for x, y in blocked)

        def dfs(x1, y1, x2, y2, x3, y3):
            if (x1, y1) in blocks:
                return False
            if (x1, y1) in visited:
                return False

            if (x1, y1) == (x3, y3):
                return True
            if (abs(x1 - x2) + abs(y1 - y2)) >= 200:
                return True

            visited.add((x1, y1))

            # 寻找目标方向
            if x3 > x1:
                aim_x = 1
            elif x3 < x1:
                aim_x = -1
            else:
                aim_x = 0

            if y3 > y1:
                aim_y = 1
            elif y3 < y1:
                aim_y = -1
            else:
                aim_y = 0

            # print((x1, y1), (x3, y3), ":", aim_x, aim_y)

            # 首先尝试向目标靠近；然后退而求其次尝试向平行方向移动；最后向着反方向移动
            if aim_x == 1 and aim_y == 1:
                if x1 < self._MAX and dfs(x1 + 1, y1, x2, y2, x3, y3):
                    return True
                if y1 < self._MAX and dfs(x1, y1 + 1, x2, y2, x3, y3):
                    return True
                if x1 > self._MIN and dfs(x1 - 1, y1, x2, y2, x3, y3):
                    return True
                if y1 > self._MIN and dfs(x1, y1 - 1, x2, y2, x3, y3):
                    return True
            if aim_x == 1 and aim_y == 0:
                if x1 < self._MAX and dfs(x1 + 1, y1, x2, y2, x3, y3):
                    return True
                if y1 < self._MAX and dfs(x1, y1 + 1, x2, y2, x3, y3):
                    return True
                if y1 > self._MIN and dfs(x1, y1 - 1, x2, y2, x3, y3):
                    return True
                if x1 > self._MIN and dfs(x1 - 1, y1, x2, y2, x3, y3):
                    return True
            if aim_x == 1 and aim_y == -1:
                if x1 < self._MAX and dfs(x1 + 1, y1, x2, y2, x3, y3):
                    return True
                if y1 > self._MIN and dfs(x1, y1 - 1, x2, y2, x3, y3):
                    return True
                if y1 < self._MAX and dfs(x1, y1 + 1, x2, y2, x3, y3):
                    return True
                if x1 > self._MIN and dfs(x1 - 1, y1, x2, y2, x3, y3):
                    return True
            if aim_x == 0 and aim_y == 1:
                if y1 < self._MAX and dfs(x1, y1 + 1, x2, y2, x3, y3):
                    return True
                if x1 < self._MAX and dfs(x1 + 1, y1, x2, y2, x3, y3):
                    return True
                if x1 > self._MIN and dfs(x1 - 1, y1, x2, y2, x3, y3):
                    return True
                if y1 > self._MIN and dfs(x1, y1 - 1, x2, y2, x3, y3):
                    return True
            if aim_x == 0 and aim_y == -1:
                if y1 > self._MIN and dfs(x1, y1 - 1, x2, y2, x3, y3):
                    return True
                if x1 < self._MAX and dfs(x1 + 1, y1, x2, y2, x3, y3):
                    return True
                if x1 > self._MIN and dfs(x1 - 1, y1, x2, y2, x3, y3):
                    return True
                if y1 < self._MAX and dfs(x1, y1 + 1, x2, y2, x3, y3):
                    return True
            if aim_x == -1 and aim_y == 1:
                if x1 > self._MIN and dfs(x1 - 1, y1, x2, y2, x3, y3):
                    return True
                if y1 < self._MAX and dfs(x1, y1 + 1, x2, y2, x3, y3):
                    return True
                if x1 < self._MAX and dfs(x1 + 1, y1, x2, y2, x3, y3):
                    return True
                if y1 > self._MIN and dfs(x1, y1 - 1, x2, y2, x3, y3):
                    return True
            if aim_x == -1 and aim_y == 0:
                if x1 > self._MIN and dfs(x1 - 1, y1, x2, y2, x3, y3):
                    return True
                if y1 < self._MAX and dfs(x1, y1 + 1, x2, y2, x3, y3):
                    return True
                if y1 > self._MIN and dfs(x1, y1 - 1, x2, y2, x3, y3):
                    return True
                if x1 < self._MAX and dfs(x1 + 1, y1, x2, y2, x3, y3):
                    return True
            if aim_x == -1 and aim_y == -1:
                if x1 > self._MIN and dfs(x1 - 1, y1, x2, y2, x3, y3):
                    return True
                if y1 > self._MIN and dfs(x1, y1 - 1, x2, y2, x3, y3):
                    return True
                if x1 < self._MAX and dfs(x1 + 1, y1, x2, y2, x3, y3):
                    return True
                if y1 < self._MAX and dfs(x1, y1 + 1, x2, y2, x3, y3):
                    return True

            # 无论向哪个方向都无法到达
            return False

        visited = set()
        ans1 = dfs(source[0], source[1], source[0], source[1], target[0], target[1])
        visited = set()
        ans2 = dfs(target[0], target[1], target[0], target[1], source[0], source[1])

        return ans1 and ans2


if __name__ == "__main__":
    # False
    print(Solution().isEscapePossible(
        blocked=[[0, 1], [1, 0]],
        source=[0, 0], target=[0, 2]))

    # True
    print(Solution().isEscapePossible(
        blocked=[], source=[0, 0],
        target=[999999, 999999]))

    # 测试用例14 : False
    print(Solution().isEscapePossible(
        blocked=[[100059, 100063], [100060, 100064], [100061, 100065], [100062, 100066], [100063, 100067],
                 [100064, 100068], [100065, 100069], [100066, 100070], [100067, 100071], [100068, 100072],
                 [100069, 100073], [100070, 100074], [100071, 100075], [100072, 100076], [100073, 100077],
                 [100074, 100078], [100075, 100079], [100076, 100080], [100077, 100081], [100078, 100082],
                 [100079, 100083], [100080, 100082], [100081, 100081], [100082, 100080], [100083, 100079],
                 [100084, 100078], [100085, 100077], [100086, 100076], [100087, 100075], [100088, 100074],
                 [100089, 100073], [100090, 100072], [100091, 100071], [100092, 100070], [100093, 100069],
                 [100094, 100068], [100095, 100067], [100096, 100066], [100097, 100065], [100098, 100064],
                 [100099, 100063], [100098, 100062], [100097, 100061], [100096, 100060], [100095, 100059],
                 [100094, 100058], [100093, 100057], [100092, 100056], [100091, 100055], [100090, 100054],
                 [100089, 100053], [100088, 100052], [100087, 100051], [100086, 100050], [100085, 100049],
                 [100084, 100048], [100083, 100047], [100082, 100046], [100081, 100045], [100080, 100044],
                 [100079, 100043], [100078, 100044], [100077, 100045], [100076, 100046], [100075, 100047],
                 [100074, 100048], [100073, 100049], [100072, 100050], [100071, 100051], [100070, 100052],
                 [100069, 100053], [100068, 100054], [100067, 100055], [100066, 100056], [100065, 100057],
                 [100064, 100058], [100063, 100059], [100062, 100060], [100061, 100061], [100060, 100062]],
        source=[100079, 100063], target=[999948, 999967]))

    # 测试用例28 : True
    print(Solution().isEscapePossible(
        blocked=[[0, 3], [1, 0], [1, 1], [1, 2], [1, 3]],
        source=[0, 0], target=[0, 2]
    ))

    # 测试用例29 : False
    print(Solution().isEscapePossible(
        blocked=[[0, 999991], [0, 999993], [0, 999996], [1, 999996], [1, 999997], [1, 999998], [1, 999999]],
        source=[0, 999997], target=[0, 2]
    ))
